The present invention relates to correction of one or more multi-state symbols in error in a sequence of symbols which can be ordered in a matrix. More specifically, it relates to error correction by first identifying the location of possible errors in a matrix of multi-state symbols, followed by reconstruction of the original symbols from the remaining symbols believed to be not in error.
Error correction in a plurality of multi-state symbols or a sequence of binary symbols representing multi-state symbols is known, especially in the field of communications and information storage or transfer. In general, a series of symbols that is being transferred may have experienced interference or noise on a transmission channel. Possibly the storage medium, such as an optical or magnetic disk, may have been damaged. As a consequence, a received sequence of multi-state symbols may be different from the sequence from which it originated. The difference between an original sequence of symbols and a received sequence may be considered to be errors.
Error control measures can be applied to detect and to correct errors. These measures in general comprise adding additional symbols to a sequence, based on the existing symbols in the original sequence. The redundancy of symbols allows for detection and sometimes correction of errors.
It usually requires a greater number of redundant symbols than errors to correct errors compared to the process of merely detecting that symbols are in errors. For instance, in data communications, wherein re-sending of information is possible and not detrimental to the quality of data transfer, it may be sufficient to detect errors and request the transmitter to resend the symbols. However, in many applications resending of symbols is impossible or undesirable. In such cases error correction is desirable and more symbols are added to a sequence of symbols to enable error correction.
Error-correction techniques for symbols in a sequence attempt to achieve the best result with as few redundant symbols as possible, and with as limited processing requirements and memory or storage requirements as possible. Error correcting redundancy is usually set to address some maximum or optimal expected symbol error ratio. If information is coded into codewords, it is to be expected that many codewords are error-free and in error-free codewords extra symbols provided for error correction or detection are truly redundant.
It is known in error correcting codes like Reed Solomon codes, which is multi-state based, that k extra symbols, which can be called check symbols, may allow at most ½k symbols in error to be corrected. Arranging of data symbols in a matrix such as a 2 dimensional matrix is known. Herein columns and rows may for instance represent a Reed Solomon codeword. Such a code is called a product code. A product code still has the disadvantage that redundancy in the codewords is not fully used to determine position of errors and based on the positions of errors in a matrix calculate the correct state for the symbols in error.
Accordingly, novel and improved methods and apparatus providing improved use of check symbols and redundancy in a multi-state symbol matrix are required.